In link analysis, data sets may be represented as collections of linked entities, and the topology and connections among the various entities can be analyzed to uncover valuable information. Each entity may symbolize a real world object, such as a person, place, physical object, business unit, phone number, and the like, and each connection between entities may represent an association or relationship between the entities. In general, entities may be represented as nodes and connections as links. Using this type of data representation, a document collection may be represented as documents connected by citations and hypertext links. As another example, an organization may be represented as individuals that are associated according to reporting assignments, social relationships, and communication patterns.
Link analysis may be “visual” or “algorithmic.” Visual link analysis presents to an analyst an image of the entities and their connections. The analyst may use the image to discover relationships or otherwise infer new knowledge. Algorithmic link analysis involves a more sophisticated and deeper analysis of the linked entities, such as the distance between two nodes and/or whether two nodes are related through a specific third node. By at least partially automating the process, algorithmic link analysis may facilitate a more efficient evaluation of connections and relationships among entities.
Applications of link analysis are typically investigative in nature. For example, terrorist investigations have increasingly involved a study of the relationships among people, common residences, banks, fund transfers, and known terrorist organizations. Link analysis may also be used in other law enforcement or fraud detection efforts to identify associations among individuals and organizations; in epidemiology to discover connections between people, animals, homes, and workplaces; in evaluating complex computer systems; and in information retrieval to analyze relationships among web pages, news stories, or other document collections. Accordingly, link analysis is potentially valuable to a wide variety of enterprises, including, for example, organizations involved with business intelligence and knowledge management.
In performing link analysis, one must first develop a topology (e.g., known links between people, things, and events). The topology may be constructed using multiple, heterogeneous data sources. The value of link analysis is in using the topology to predict and infer previously unknown relationships among entities. Such predictions and inferences may be made, for example, by looking at the distance (e.g., the number of links) between entities, a connection between two entities through a specific third entity, or a pattern of events. For example, by examining a set of activities, it may be possible to discover a relationship between entities or to predict an upcoming event.